package formal.linkedList;

/**
 * 合并两个有序链表
 *
 * @author DengYuan2
 * @create 2021-01-06 20:28
 */
public class E_21 {
    public static void main(String[] args) {
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        ListNode n4 = new ListNode(4);
        n1.next = n2;
        n2.next = n4;
        ListNode m1 = new ListNode(1);
        ListNode m3 = new ListNode(3);
        ListNode m4 = new ListNode(4);
        m1.next = m3;
        m3.next = m4;
        ListNode listNode = mergeTwoLists2(n1, m1);
        System.out.println(listNode);

    }

    /**
     * 我的写法1：将节点按照数值大小插入到新的链表中
     * @param l1
     * @param l2
     * @return
     */
    public static ListNode mergeTwoLists1(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        ListNode tmp = new ListNode(-1);
        ListNode t = tmp;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                t.next = l1;
                l1 = l1.next;
            } else {
                t.next = l2;
                l2 = l2.next;
            }
            t = t.next;

        }
        if (l1 == null) {
            t.next = l2;
        }
        if (l2 == null) {
            t.next = l1;
        }
        return tmp.next;

    }

    /**
     * 我的写法2：一个链表插入另一个链表
     * @param l1
     * @param l2
     * @return
     */
    public static ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        ListNode firstNode = (l1.val <= l2.val) ? l1 : l2;
        ListNode secondNode = (l1.val > l2.val) ? l1 : l2;
        ListNode pre = firstNode;
        ListNode cur = firstNode.next;
        ListNode tmp = secondNode;
        while (cur!=null && tmp!=null){
            if (pre.val<=tmp.val&&tmp.val<=cur.val){
                ListNode m = tmp.next;
                pre.next=tmp;
                tmp.next=cur;
                tmp = m;
                pre=pre.next;
            }else {
                pre=pre.next;
                cur=cur.next;
            }

        }
        if (cur==null){
            pre.next=tmp;
        }
        return firstNode;

    }

    /**
     * 官方-递归
     * @param l1
     * @param l2
     * @return
     */
    public static ListNode mergeTwoLists3(ListNode l1,ListNode l2){
        if (l1==null){
            return l2;
        }
        if (l2==null){
            return l1;
        }
        if (l1.val<l2.val){
            l1.next=mergeTwoLists3(l1.next,l2);
            return l1;
        }else {
            l2.next=mergeTwoLists3(l1,l2.next);
            return l2;
        }
    }
}
